/* 
    搜索插入位置

    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    请必须使用时间复杂度为 O(log n) 的算法。

    输入: nums = [1,3,5,6], target = 5
    输出: 2

    输入: nums = [1,3,5,6], target = 2
    输出: 1

    输入: nums = [1,3,5,6], target = 0
    输出: 0

    输入: nums = [1], target = 0
    输出: 0

    输入: nums = [1,3,5,6], target = 7
    输出: 4
*/

{
  /**
   * 借用数组的splice方法在指定位置插入
   * @param {*} nums
   * @param {*} target
   */
  var searchInsert = function (nums, target) {
    let len = nums.length,
      low = 0,
      high = len - 1,
      pos = 0;

    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (target >= nums[mid]) {
        low = mid + 1;
      } else {
        pos = mid;
        high = mid - 1;
      }
    }
    return pos;
  };
  const nums = [1, 3, 5, 6],
    target = 2;
  console.log(searchInsert(nums, target));
}
